using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace HashMap_Ex
{
    public class Node<T>
    {
        public T value;
        public Node<T> parent;
        public bool isRed;
        public Node<T> left;
        public Node<T> right;
    }

    public class RBTreeNode<T> where T : IComparable
    {
        private T value; //node value
        private RBTreeNode<T> left; //left child pointer
        private RBTreeNode<T> right; //right child pointer
        private RBTreeNode<T> parent; //parent pointer
        private bool red; //color is red or not red

        public RBTreeNode()
        {
        }

        public RBTreeNode(T value)
        {
            this.value = value;
        }

        public RBTreeNode(T value, bool isRed)
        {
            this.value = value;
            this.red = isRed;
        }

        public T getValue()
        {
            return value;
        }

        internal void setValue(T value)
        {
            this.value = value;
        }

        public RBTreeNode<T> getLeft()
        {
            return left;
        }

        public void setLeft(RBTreeNode<T> left)
        {
            this.left = left;
        }

        public RBTreeNode<T> getRight()
        {
            return right;
        }

        internal void setRight(RBTreeNode<T> right)
        {
            this.right = right;
        }

        internal RBTreeNode<T> getParent()
        {
            return parent;
        }

        internal void setParent(RBTreeNode<T> parent)
        {
            this.parent = parent;
        }

        internal bool isRed()
        {
            return red;
        }

        internal bool isBlack()
        {
            return !red;
        }

        /**
	* is leaf node
	**/
        bool isLeaf()
        {
            return left == null && right == null;
        }

        internal void setRed(bool red)
        {
            this.red = red;
        }

        internal void makeRed()
        {
            red = true;
        }

        internal void makeBlack()
        {
            red = false;
        }

        public string tostring()
        {
            return value.ToString();
        }
    }


    public class RBTree<T> where T : IComparable
    {
        private readonly RBTreeNode<T> root;

        //node number
        private long size = 0;

        //in overwrite mode,all node's value can not  has same	value
        //in non-overwrite mode,node can have same value, suggest don't use non-overwrite mode.
        private volatile bool overrideMode = true;

        public RBTree()
        {
            this.root = new RBTreeNode<T>();
        }

        public RBTree(bool overrideMode):this()
        {
            this.overrideMode = overrideMode;
        }


        public bool isOverrideMode()
        {
            return overrideMode;
        }

        public void setOverrideMode(bool overrideMode)
        {
            this.overrideMode = overrideMode;
        }

        /**
	 * number of tree number
	 * @return
	 */
        public long getSize()
        {
            return size;
        }

        /**
	 * get the root node
	 * @return
	 */
        public RBTreeNode<T> getRoot()
        {
            return root.getLeft();
        }

        /**
	 * add value to a new node,if this value exist in this tree,
	 * if value exist,it will return the exist value.otherwise return null
	 * if override mode is true,if value exist in the tree,
	 * it will override the old value in the tree
	 * 
	 * @param value
	 * @return
	 */
        public T addNode(T value)
        {
            RBTreeNode<T> t = new RBTreeNode<T>(value);
            return addNode(t);
        }

        /**
	 * find the value by give value(include key,key used for search,
	 * other field is not used,@see compare method).if this value not exist return null
	 * @param value
	 * @return
	 */
        public T find(T value)
        {
            RBTreeNode<T> dataRoot = getRoot();
            while (dataRoot != null)
            {
                int cmp = dataRoot.getValue().CompareTo(value);
                if (cmp < 0)
                {
                    dataRoot = dataRoot.getRight();
                }
                else if (cmp > 0)
                {
                    dataRoot = dataRoot.getLeft();
                }
                else
                {
                    return dataRoot.getValue();
                }
            }

            return default(T);
        }

        /**
	 * remove the node by give value,if this value not exists in tree return null
	 * @param value include search key
	 * @return the value contain in the removed node
	 */
        public T remove(T value)
        {
            RBTreeNode<T> dataRoot = getRoot();
            RBTreeNode<T> parent = root;

            while (dataRoot != null)
            {
                int cmp = dataRoot.getValue().CompareTo(value);
                if (cmp < 0)
                {
                    parent = dataRoot;
                    dataRoot = dataRoot.getRight();
                }
                else if (cmp > 0)
                {
                    parent = dataRoot;
                    dataRoot = dataRoot.getLeft();
                }
                else
                {
                    if (dataRoot.getRight() != null)
                    {
                        RBTreeNode<T> min = removeMin(dataRoot.getRight());
                        //x used for fix color balance
                        RBTreeNode<T> x = min.getRight() == null ? min.getParent() : min.getRight();
                        bool isParent = min.getRight() == null;

                        min.setLeft(dataRoot.getLeft());
                        setParent(dataRoot.getLeft(), min);
                        if (parent.getLeft() == dataRoot)
                        {
                            parent.setLeft(min);
                        }
                        else
                        {
                            parent.setRight(min);
                        }

                        setParent(min, parent);

                        bool curMinIsBlack = min.isBlack();
                        //inherit dataRoot's color
                        min.setRed(dataRoot.isRed());

                        if (min != dataRoot.getRight())
                        {
                            min.setRight(dataRoot.getRight());
                            setParent(dataRoot.getRight(), min);
                        }

                        //remove a black node,need fix color
                        if (curMinIsBlack)
                        {
                            if (min != dataRoot.getRight())
                            {
                                fixRemove(x, isParent);
                            }
                            else if (min.getRight() != null)
                            {
                                fixRemove(min.getRight(), false);
                            }
                            else
                            {
                                fixRemove(min, true);
                            }
                        }
                    }
                    else
                    {
                        setParent(dataRoot.getLeft(), parent);
                        if (parent.getLeft() == dataRoot)
                        {
                            parent.setLeft(dataRoot.getLeft());
                        }
                        else
                        {
                            parent.setRight(dataRoot.getLeft());
                        }

                        //current node is black and tree is not empty
                        if (dataRoot.isBlack() && !(root.getLeft() == null))
                        {
                            RBTreeNode<T> x = dataRoot.getLeft() == null
                                ? parent
                                : dataRoot.getLeft();
                            bool isParent = dataRoot.getLeft() == null;
                            fixRemove(x, isParent);
                        }
                    }

                    setParent(dataRoot, null);
                    dataRoot.setLeft(null);
                    dataRoot.setRight(null);
                    if (getRoot() != null)
                    {
                        getRoot().setRed(false);
                        getRoot().setParent(null);
                    }

                    --size;
                    return dataRoot.getValue();
                }
            }

            return default(T);
        }

        /**
	 * fix remove action
	 * @param node
	 * @param isParent
	 */
        private void fixRemove(RBTreeNode<T> node, bool isParent)
        {
            RBTreeNode<T> cur = isParent ? null : node;
            bool isRed = isParent ? false : node.isRed();
            RBTreeNode<T> parent = isParent ? node : node.getParent();

            while (!isRed && !isRoot(cur))
            {
                RBTreeNode<T> sibling = getSibling(cur, parent);
                //sibling is not null,due to before remove tree color is balance

                //if cur is a left node
                bool isLeft = parent.getRight() == sibling;
                if (sibling.isRed() && !isLeft)
                {
                    //case 1
                    //cur in right
                    parent.makeRed();
                    sibling.makeBlack();
                    rotateRight(parent);
                }
                else if (sibling.isRed() && isLeft)
                {
                    //cur in left
                    parent.makeRed();
                    sibling.makeBlack();
                    rotateLeft(parent);
                }
                else if (isBlack(sibling.getLeft()) && isBlack(sibling.getRight()))
                {
                    //case 2
                    sibling.makeRed();
                    cur = parent;
                    isRed = cur.isRed();
                    parent = parent.getParent();
                }
                else if (isLeft && !isBlack(sibling.getLeft())
                                && isBlack(sibling.getRight()))
                {
                    //case 3
                    sibling.makeRed();
                    sibling.getLeft().makeBlack();
                    rotateRight(sibling);
                }
                else if (!isLeft && !isBlack(sibling.getRight())
                                 && isBlack(sibling.getLeft()))
                {
                    sibling.makeRed();
                    sibling.getRight().makeBlack();
                    rotateLeft(sibling);
                }
                else if (isLeft && !isBlack(sibling.getRight()))
                {
                    //case 4
                    sibling.setRed(parent.isRed());
                    parent.makeBlack();
                    sibling.getRight().makeBlack();
                    rotateLeft(parent);
                    cur = getRoot();
                }
                else if (!isLeft && !isBlack(sibling.getLeft()))
                {
                    sibling.setRed(parent.isRed());
                    parent.makeBlack();
                    sibling.getLeft().makeBlack();
                    rotateRight(parent);
                    cur = getRoot();
                }
            }

            if (isRed)
            {
                cur.makeBlack();
            }

            if (getRoot() != null)
            {
                getRoot().setRed(false);
                getRoot().setParent(null);
            }
        }

        //get sibling node
        private RBTreeNode<T> getSibling(RBTreeNode<T> node, RBTreeNode<T> parent)
        {
            parent = node == null ? parent : node.getParent();
            if (node == null)
            {
                return parent.getLeft() == null ? parent.getRight() : parent.getLeft();
            }

            if (node == parent.getLeft())
            {
                return parent.getRight();
            }
            else
            {
                return parent.getLeft();
            }
        }

        private bool isBlack(RBTreeNode<T> node)
        {
            return node == null || node.isBlack();
        }

        private bool isRoot(RBTreeNode<T> node)
        {
            return root.getLeft() == node && node.getParent() == null;
        }

        /**
	 * find the successor node
	 * @param node current node's right node
	 * @return
	 */
        private RBTreeNode<T> removeMin(RBTreeNode<T> node)
        {
            //find the min node
            RBTreeNode<T> parent = node;
            while (node != null && node.getLeft() != null)
            {
                parent = node;
                node = node.getLeft();
            }

            //remove min node
            if (parent == node)
            {
                return node;
            }

            parent.setLeft(node.getRight());
            setParent(node.getRight(), parent);

            //don't remove right pointer,it is used for fixed color balance
            //node.setRight(null);
            return node;
        }


        private T addNode(RBTreeNode<T> node)
        {
            node.setLeft(null);
            node.setRight(null);
            node.setRed(true);
            setParent(node, null);
            if (root.getLeft() == null)
            {
                root.setLeft(node);
                //root node is black
                node.setRed(false);
                ++size;
            }
            else
            {
                RBTreeNode<T> x = findParentNode(node);
                var temp = x.getValue();
                int cmp =x.getValue().CompareTo(node.getValue());

                if (this.overrideMode && cmp == 0)
                {
                    T v = x.getValue();
                    x.setValue(node.getValue());
                    return v;
                }
                else if (cmp == 0)
                {
                    //value exists,ignore this node
                    return x.getValue();
                }

                setParent(node, x);

                if (cmp > 0)
                {
                    x.setLeft(node);
                }
                else
                {
                    x.setRight(node);
                }

                fixInsert(node);
                ++size;
            }

            return default(T);
        }

        /**
	 * find the parent node to hold node x,if parent value equals x.value return parent.
	 * @param x
	 * @return
	 */
        private RBTreeNode<T> findParentNode(RBTreeNode<T> x)
        {
            RBTreeNode<T> dataRoot = getRoot();
            RBTreeNode<T> child = dataRoot;

            while (child != null)
            {
                int cmp = child.getValue().CompareTo(x.getValue());
                if (cmp == 0)
                {
                    return child;
                }

                if (cmp > 0)
                {
                    dataRoot = child;
                    child = child.getLeft();
                }
                else if (cmp < 0)
                {
                    dataRoot = child;
                    child = child.getRight();
                }
            }

            return dataRoot;
        }

        /**
	 * red black tree insert fix.
	 * @param x
	 */
        private void fixInsert(RBTreeNode<T> x)
        {
            RBTreeNode<T> parent = x.getParent();

            while (parent != null && parent.isRed())
            {
                RBTreeNode<T> uncle = getUncle(x);
                if (uncle == null)
                {
                    //need to rotate
                    RBTreeNode<T> ancestor = parent.getParent();
                    //ancestor is not null due to before before add,tree color is balance
                    if (parent == ancestor.getLeft())
                    {
                        bool isRight = x == parent.getRight();
                        if (isRight)
                        {
                            rotateLeft(parent);
                        }

                        rotateRight(ancestor);

                        if (isRight)
                        {
                            x.setRed(false);
                            parent = null; //end loop
                        }
                        else
                        {
                            parent.setRed(false);
                        }

                        ancestor.setRed(true);
                    }
                    else
                    {
                        bool isLeft = x == parent.getLeft();
                        if (isLeft)
                        {
                            rotateRight(parent);
                        }

                        rotateLeft(ancestor);

                        if (isLeft)
                        {
                            x.setRed(false);
                            parent = null; //end loop
                        }
                        else
                        {
                            parent.setRed(false);
                        }

                        ancestor.setRed(true);
                    }
                }
                else
                {
                    //uncle is red
                    parent.setRed(false);
                    uncle.setRed(false);
                    parent.getParent().setRed(true);
                    x = parent.getParent();
                    parent = x.getParent();
                }
            }

            getRoot().makeBlack();
            getRoot().setParent(null);
        }

        /**
	 * get uncle node
	 * @param node
	 * @return
	 */
        private RBTreeNode<T> getUncle(RBTreeNode<T> node)
        {
            RBTreeNode<T> parent = node.getParent();
            RBTreeNode<T> ancestor = parent.getParent();
            if (ancestor == null)
            {
                return null;
            }

            if (parent == ancestor.getLeft())
            {
                return ancestor.getRight();
            }
            else
            {
                return ancestor.getLeft();
            }
        }

        private void rotateLeft(RBTreeNode<T> node)
        {
            RBTreeNode<T> right = node.getRight();
            if (right == null)
            {
                throw new Exception("right node is null");
            }

            RBTreeNode<T> parent = node.getParent();
            node.setRight(right.getLeft());
            setParent(right.getLeft(), node);

            right.setLeft(node);
            setParent(node, right);

            if (parent == null)
            {
                //node pointer to root
                //right  raise to root node
                root.setLeft(right);
                setParent(right, null);
            }
            else
            {
                if (parent.getLeft() == node)
                {
                    parent.setLeft(right);
                }
                else
                {
                    parent.setRight(right);
                }

                //right.setParent(parent);
                setParent(right, parent);
            }
        }

        private void rotateRight(RBTreeNode<T> node)
        {
            RBTreeNode<T> left = node.getLeft();
            if (left == null)
            {
                throw new Exception("left node is null");
            }

            RBTreeNode<T> parent = node.getParent();
            node.setLeft(left.getRight());
            setParent(left.getRight(), node);

            left.setRight(node);
            setParent(node, left);

            if (parent == null)
            {
                root.setLeft(left);
                setParent(left, null);
            }
            else
            {
                if (parent.getLeft() == node)
                {
                    parent.setLeft(left);
                }
                else
                {
                    parent.setRight(left);
                }

                setParent(left, parent);
            }
        }


        private void setParent(RBTreeNode<T> node, RBTreeNode<T> parent)
        {
            if (node != null)
            {
                node.setParent(parent);
                if (parent == root)
                {
                    node.setParent(null);
                }
            }
        }

        /**
	 * debug method,it used print the given node and its children nodes,
	 * every layer output in one line
	 * @param root
	 */
        public void printTree(RBTreeNode<T> root)
        {
            List<RBTreeNode<T>> queue = new List<RBTreeNode<T>>();
            List<RBTreeNode<T>> queue2 = new List<RBTreeNode<T>>();
            if (root == null)
            {
                return;
            }

            queue.Add(root);
            bool firstQueue = true;

            while (queue.Count > 0 || queue2.Count > 0)
            {
                List<RBTreeNode<T>> q = firstQueue ? queue : queue2;
                RBTreeNode<T> n = null;
                if (q.Count > 0)
                {
                    n = q.First();
                    q.RemoveAt(0);
                }
                if (n != null)
                {
                    string pos = n.getParent() == null
                        ? ""
                        : (n == n.getParent().getLeft()
                            ? " LE"
                            : " RI");
                    string pstr = n.getParent() == null ? "" : n.getParent().tostring();
                    string cstr = n.isRed() ? "R" : "B";
                    cstr = n.getParent() == null ? cstr : cstr + " ";
                    Console.WriteLine(n + "(" + (cstr) + pstr + (pos) + ")" + "\t");
                    if (n.getLeft() != null)
                    {
                        (firstQueue ? queue2 : queue).Add(n.getLeft());
                    }

                    if (n.getRight() != null)
                    {
                        (firstQueue ? queue2 : queue).Add(n.getRight());
                    }
                }
                else
                {
                    Console.WriteLine();
                    firstQueue = !firstQueue;
                }
            }
        }


        public static void main(string[] args)
        {
            RBTree<string> bst = new RBTree<string>();
            bst.addNode("d");
            bst.addNode("d");
            bst.addNode("c");
            bst.addNode("c");
            bst.addNode("b");
            bst.addNode("f");
            
            bst.addNode("a");
            bst.addNode("e");
            
            bst.addNode("g");
            bst.addNode("h");
            
            
            bst.remove("c");
            
            bst.printTree(bst.getRoot());
        }
    }
}